class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.empty()) return nullptr;
        vector<ListNode*> list;
        for (auto & l : lists) if (l) list.push_back(l);
        make_heap(list.begin(), list.end(), [](const ListNode* a, const ListNode* b){return a->val > b->val;});
        ListNode* dummy = new ListNode(0);
        ListNode* tail = dummy;
        while (!list.empty()) {
            pop_heap(list.begin(), list.end(), [](const ListNode* a, const ListNode* b){return a->val > b->val;});
            ListNode* tmp = list.back();
            list.pop_back();
            if (tmp == nullptr) continue;
            tail->next = tmp;
            tail = tail->next;
            if (tail->next != nullptr) {
                list.push_back(tail->next);
                push_heap(list.begin(), list.end(), [](const ListNode* a, const ListNode* b){return a->val > b->val;});
            }
        }
        return dummy->next;
    }
};